Title: oxford / 319 game theory

Front: df strategic game

Front: df strategic game with vNM preferences
Back: [latex]
A \textbf{strategic} game with vNM preferences is a triple of:
\begin{itemize}
\item a finite set $N$ (the set of \textbf{players})
\item for each player $i \in N$ a nonempty set $A_i$ (the set of \textbf{actions} available to player $i$)
\item for each player $i \in N$ a preference function $u_i$ with $u_i: A \rightarrow \mathbb{R}$.
\end{itemize}
[/latex]

Front: df outcome, set of outcomes
Back: [latex]We refer to an action profile $a = (a_j )_{j \in N}$ as an \textbf{outcome}. We denote the set $\{A_1 \times A_2 \times ... \times A_j \} = \times_{j\in N}A_j $ of outcomes by $A$.
We refer to a profile of mixed strategies $\alpha = (\alpha_i)_{j \in N}$ as an outcome in mixed strategies. The set of outcomes in mixed strategies is $\times_{j \in N} \Delta A_j$.
 [/latex]

Front: df mixed extension

Front: df mixed strategy nash equilibrium

Front: df nash equilibrium

Front: existence of mixed strategy nash equilibrium

Front: characterisation of mixed strategy nash equilibrium

Front: nash equilibria with no weakly dominated strategies

Front: translating between mixed and pure strategy equilibria
Back: [latex]
Proposition: Let $a^*$ be a Nash equilibrium of G. Let $\alpha^*$ be such that for each $i \in N$, $\alpha_i^*$ assings probability 1 to $a_i^*$. Then $\alpha^*$ is a mixed strategy Nash equilibrium of G. [Adapted from proposition 120.1]
[/latex]
[latex]Proposition: let $\alpha^*$ be a mixed strategy Nash equilibrium of G such that for each $i \in N$, $\alpha_i^*$ assigns probability 1 to $a_i^*$. Then $a^*$ is a Nash equilibrium of G. [Adapted from proposition 120.2]
[/latex]

Front: df symmetric game
Back: [latex]a two-player strategic game with $N=\{1,2\}$ is symmetric iff \\ \\$A_1=A_2$ and [ $(up,down) \succsim_1 (left,right)$ iff $(down,up) \succsim_2 (right,left)$ for all $up,down,left,right \in A_1$]
\bigskip
Example symmetric: prisoners' dilemma, chicken
Example non-symmetric: matching pennies, BoS
[/latex]

Front: df symmetric game with ordinal preferences

Front: existence of symmetric equilibrium
Back: Every symmetric strategic game with vNM preferences in which each player's set of actions is finite has a symmetric mixed strategy Nash equilibrium.

Front: BoS
Back: Mixed Strategy Nash Equilibria:
p=1     q=1 [Bach,Bach]
p=0     q=0 [Stravinsky,Stravinsky]
p=2/3  q=1/3
A game that involves both coordination and competition

Front: A pure Coordination Game
Back: Pure coordination game:
Mixed Strategy Nash equilibria:
p=1 q=1 [Mozart, Mozart]
p=0 q=0 [Mahler, Mahler]
p=1/3 q=1/3

Front: Hawk-Dove
Back: Mixed Strategy Nash Equilbria
p=0 q=1 [Hawk,Dove]
p=1 q=0 [Dove,Hawk]
p=1/2 q=1/2
A game that involves both coordination and competition

Front: A strictly competitive game
Back: mixed strategy nash equilibria:
p=1/2 q=1/2

Front: rationalisability [definition]
Back: [latex]
An action $a_i \in A_i$ is rationalisable in the strategic game $\langle N, (A_i), (u_i) \rangle$ iff for each $j \in N$ there is a set $Z_j \subseteq A_j$ such that: \begin{itemize}
\item $a_i \in Z_i$
\item every action $a_j \in Z_j$ is a best response to some belief of player $j$ that assigns positive probability only to action profiles in $Z_{-j}$ \end{itemize}
[Adapted from definition 55.1]
Note: $Z_j$ is a set of rationalisable actions for player $j$. The set $R_j$ of rationalisable actions for $j$ is the largest set that satisfies the defintion. The set of profiles of rationalisable actions is $\times_{j\in N} R_j$.
[/latex]

Front: strict domination [definition]

Front: weak domination

Front: iterated elimination [proposition]
Back: [latex]Proposition: For any finite strategic game $\langle N, (A_i), (u_i) \rangle$, for each $j \in N$ the set $R_j$ of player $j$'s rationalisable actions is equal to the set $X_j$ of player $j$'s actions which survive iterated elimination of strictly dominated strategies. [Adapted from proposition 61.2]
\bigskip
Note: the proposition fails if we modify the definition of rationalizability to require the players to believe that their opponents’ actions are independent. Then $R_j \subseteq X_j$. This does not affect two-player games.[/latex]

Front: bayesian-nash equilibrium of a bayesian game
Back: Intuitive gloss:
BNE specifies for each player a mapping from signals to actions such that, for every state of the world, each player is best responding given their signal and given other players' mapping from signal to actions.
Other fields (not shown on cards):
notes: A Bayesian-Nash equilibrium of the Bayesian game $\langle N, \Omega,(A_i), (T_i), (s_i), (p_i), (u_i) \rangle$ is a Nash Equilibrium of the strategic game with vNM preferences defined as follows:
* The set of players is the set of all pairs $(i,t_i)$ for $i \in N$ and $t_i \in T_i$
* For each player $(i,t_i)$, the set of actions is $A_i$
* For each player $(i,t_i)$, the preference function assigns to action $a_i$ the payoff
$$\sum_{\omega \in \Omega} p_i(\omega \mid t_i )u_i [(a_i,\hat{a}_{-i}(\omega)), \omega ]$$
where $\hat{a}_{-i}(\omega)$ is the profile of actions taken by every player $(j,s_j(\omega)), j \neq i$ in state $\omega$.
[adapted from definition 281.2]a

Front: bayesian game

Front: correlated equilibrium
Other fields (not shown on cards):
notes: For the strategic game $G=\langle N, (A_i), (u_i) \rangle$, we can define:
* a finite probability space $(\Omega,\pi)$, where $\Omega$ is the set of states and $\pi$ is a probability measure on $\Omega$.
* for each player $i \in N$, a partition $P_i$ of $\Omega$ ("information partition")
* for each player $i \in N$, a function $\sigma_i: \Omega \rightarrow A_i$ such that for any $w_2, w_2 \in p_i$ for $p_i \in P_i$, $\sigma_i(w_1)=\sigma_i(w_2)$. ("correlated strategy")
A correlated equilibrium of $G$ is a triple $\langle (\Omega,\pi)^*, (P_i)^* ,(\sigma_i)^*\rangle$ such that for all $i$, for every correlated strategy $\sigma_i$ of player $i$, we have
$$\sum_{w \in \Omega} \pi(w) u_i(\sigma_{-i}^*(w), \sigma_{i}^*(w)) \geq \sum_{w \in \Omega} \pi(w) u_i (\sigma_{-i}^*(w), \sigma_{i}(w))$$

Front: equilibrium and rationalisability

Front: strict domination [characterisation]

Front: information partition
Back: partition of a set is a grouping of the set's elements into non-empty subsets, in such a way that every element is included in one and only one of the subsets. an information partition is a partition of a state space.

Front: knowledge function
Back: This is defined in general, but usually only interesting if P is an information partition.

Front: common knowledge
Back: the two definitions are equivalent.

Front: self-evidence and information partitions

Front: aumann's agreement theorem

Front: knowledge and nash equilibrium

Front: knowledge and rationalisability

Front: extensive game with perfect information
Back: adapted from definition 89.1
Other fields (not shown on cards):
notes: an extensive game with perfect information is a quadruple $\langle N,H,P,(\succsim_i) \rangle$ where
* $N$ is a finite set ("players")
* $H$ is a set of sequences ("histories") such that some formal criteria are met [see definition 89.1]. A history $(a^k)_{k=1,...,K} \in H$ is terminal if it in infinite or if there is no $a^{K+1}$ such that $(a^k)_{k=1,...,K+1} \in H$. The set of terminal histories is denoted $Z$.
* $P$ is a function ("player function") that assigns to each nonterminal history (each member of $H \setminus Z$ ) a member of $N$. $P(h)$ is the player who takes an action after history $h$.
* for each player $i$, $\succsim_i$ is a preference relation on $Z$.

Front: strategy in an extensive game with perfect info

Front: nash equilibrium of extensive game with perfect information
Back: the definitions are equivalent.

Front: subgame

Front: subgame perfect equilibrium

Front: extensive game equilibrium existence

Front: bargaining game of alternating offers
Back: [latex]The two-player bargaining game with alternate offers in which payer $i$ has a discount factor $\delta_i$ has a unique subgame perfect equilibrium in which
\begin{itemize}
\item player 1 always proposes $x^*$ and accepts a proposal $y$ iff $y_1 \geq y_1^*$
\item player 2 always proposes $y^*$ and accepts a proposal $x$ iff $x_2 \geq x_2^*$
\end{itemize}
where $$x^* = (\frac{1-\delta_2}{1-\delta_1 \delta_2} , \frac{\delta_2 (1-\delta_1)}{1-\delta_1 \delta_2})$$ and $$y^*= ( \frac{\delta_1 (1-\delta_2)}{1-\delta_1 \delta_2}, \frac{1-\delta_1}{1-\delta_2 \delta_2}) $$.[/latex]

Front: one-deviation property
Back: a strategy profile s* in an extensive game may satisfy the one-deviation property:
there is no player i, and no history h after which i is the first mover, such that i can gain by deviating from s* in the first period of the subgame after h and otherwise following s*.

Front: characterisation of subgame perfect equilibrium
Back: a strategy profile s* in an extensive game with perfect information and a finite horizon is a subgame perfect equilibrium iff there is no player i, and no history h after which i is the first mover, such that i can gain by deviating from s* in the first period of the subgame after h and otherwise following s*. [i.e. iff s* satisfies the one-deviation property]

Front: desiderata for bargaining solutions
Back: [latex]
PAR. Let $(U,d)$ be a bargaining problem and let $(v_1,v_2)$ and $(v_1',v_2')$ be members of $U$. If $v_1 > v_1'$ and $v_2 > v_2'$, then the  bargaining solution does not assign $(v_1',v_2')$ to $(U,d)$. \bigskip
SYM. Let $(U,d)$ be a bargaining problem for which $(v_1,v_2)$ is in $U$ iff $(v_2,v_1)$ is in $U$, and $d_1=d_2$. Then the pair $(v_1^*,v_2^*)$ of payoffs the bargaining solution assings to $(U,d)$ satisfies $v_1^*=v_2^*$. \bigskip
INV. Let $(U,d)$ be a bargaining problem, and let $\alpha_i$ and $\beta_i$ be numbers with $\alpha_i>0$ for $i=1,2$. Let $U'$ be the set of all pairs $(\alpha_1v_1 + \beta_1 , \alpha_2 v_2 + \beta_2)$ where $(v_1,v_2)$ is a member of $U$, and let $d'=(\alpha_1 d_1 + \beta_1, \alpha_2 d_2 + \beta_2)$. If the bargaining solution assigns $(w_1,w_2)$ to $(U,d)$, then it assigns $(\alpha_1 w_2 + \beta_1, \alpha_2 w_2 + \beta_2)$ to $(U',d')$. \bigskip
IIA. Let $(U,d)$ and $(U',d')$ be bargaining problems for which $U'$ is a subset of $U$ and $d=d'$. If the agreement the bargaining solution assings to $(U,d)$ is in $U'$, then the bargaining solution assings the same agreement to $(U',d')$.
[/latex]

Front: Nash bargaining solution
Back: [latex]
A unique bargaining solution satisfies the axioms INV, SYM, PAR, IIA. This solution assigns to the bargaining problem $(U,d)$ the pair of payoffs $(v_1,v_2)$ that solves
$$\max_{v_1,v_2} (v_1-d_1)(v_2-d_2)$$ subject to $(v_1,v_2)\in U$ and $(v_1,v_2)\geq (d_1,d_2)$
[/latex]

Front: relation between strategic and axiomatic models of bargaining
Back: The subgame perfect equilibrium outcome of the variant of the bargaining game of alternating offers with risk of breakdown (and discount factors of 1 for each player) converges to the Nash bargaining solution of the associated bargining problem as the probability of breakdown tends towards 0.

Front: feasible payoff profile

Front: minmax payoff

Front: enforceable
Back: [latex]Let $v_i$ be player $i$'s minmax payoff. A payoff profile $w$ for which $w_i \geq v_i$ for all $i \in N$ is called enforceable. If $w_i > v_i$ for all $i \in N$ then $w$ is strictly enforceable. An outcome is (strictly) enforceable iff it supports a (strictly) enforceable payoff profile.[/latex]

Front: Nash equilibrium of infinitely repeated game [property]
Back: [latex]For any $\delta \in (0,1)$, every Nash equilibrium payoff profile of the infinitely repeated $\delta$-discounted game of $G$ is an enforceable payoff profile of $G$. [Adapted from proposition 144.1] [/latex]

Front: Nash folk theorem for infinitely repeated games
Back: intuitive gloss: If delta sufficiently close to 1, then a NE exists with payoffs arbitrarily close to a strictly enforceable feasible payoff of the stage game

Front: Perfect folk theorem for infinitely repeated games

Front: characterisation of subgame perfect equilibrium in infinitely repeated game
Back: Lemma 153.1
A strategy profie s* is a subgame perfect equilibrium of the delta-discounted infinitely repeated game of G if and only if there is no player i, and no history h, such that i can gain be deviating from s* in a single period after h. [i.e. iff s* satisfies the one-deviation property]

Front: purification
Back: For any strategic game G, we can create a perturbed game G' (a bayesian game) by adding to the players' payoffs noise that is:
* independently distributed
* uniformly distributed on [0,e]
Theorem:
For any MSNE \alpha* of a game G, G' has a Bayesian Nash equilibrium a* in pure strategies such that:
* In a*, each player-type strictly prefers her equilibrium strategy.
* As e tends to zero, the probability distributions over pure strategies induced by a* converge to the distribution \alpha*.
Notes:
* Harsanyi's rationale for a mixed strategy equilibrium is that even if no player makes any effort to use his pure strategies with the required probabilities, the random variations in the payoff functions induce each player to choose his pure strategies with the right frequencies.
* Strong assumptions: perturbations are independent, uniformly distributed

Front: global games
Back: bayesian games where the players' signals (their types) are correlated.
Players receive a private signal of their payoffs in the game (their type). This indicates the likely signal received by an opponent (their opponent's type).
Global games often generate a unique, easy-to-understand, and intuitive Bayesian-Nash equilibrium.

Front: correlated equilibrium [interpretation]
Back: Does the notion of correlated equilibrium provide a reasonable generalisation of mixed-strategy Nash equilibrium?
Mathematically speaking: the set of mixed strategy nash equilibria is a subset of the set of correlated equilibria.
Is this reasonable? Depends on interpretation of MSNE.
* If we take mixed strategies to be pure strategies in a larger game (in which players randomly receive private info inconsequential from the point of view of the other players), then correlated equilibrium is reasonable: the inconsequential information signals may well be correlated.
* If we take the mixed strategies more literally, as mental randomisations, then correlated equilibrium is less reasonable, since the players' "mental coin flips" should not be correlated.

Front: extensive game
Back: [latex]An extensive game is a sixtuple $\langle N,H,P,f_c,(I_i),(\succsim_i) \rangle$ where:[/latex]

Front: representations of games
Back: - strategic or normal form (synonymous)
  - show all strategies in a payoff matrix
- reduced normal form
  - normal form with duplicate strategies (those that do not affect payoffs) removed
- extensive form
  - Directed graph with a single initial node; edges represent moves.
  - Probabilities on edges representing Nature (chance) moves. [none if extensive game with perfect information]
  - Nodes that the deciding player cannot distinguish (which are in the same information set) are connected by a dashed line. [none if extensive game with perfect information]

Front: finite horizon extensive game
Back: If the length of the longest terminal history of an extensive game is finite, we say that the game has a finite horizon
Even a game with a finite horizon may have infinitely many terminal histories, because some player has infintely many actions after some history. If a game has a finite horizon and finitely many terminal histories we say it is finite.
Other fields (not shown on cards):
notes: taken from Osborne p 157

Front: bargaining game of alternating offers (df)
Back: Key points:
* no dealine: each player, after rejecting an offer, always has the opportunity to make a counteroffer
* player 1 makes the first offer
* pie to be divided is of size 1

Front: how many minutes per question in game theory exam?
Back: 56 minutes per question
(225 minutes (180 + 45 extra) / 4 questions)

Front: psychological game
Back: [latex]In psychological games the payoff to $i$ of playing $a_i$ depends not only on $a_{-i}$, but also on what $i$ thinks $-i$ believe, and on what $i$ thinks $-i$ believe others believe, and so on. In equilibrium, beliefs are assumed to correspond to reality. [/latex]

Front: intuitive criterion df
Back: a PBE satisfies the Intuitive Criterion iff each player, upon observing a deviation, puts zero weight on types whose equilibrium payoff exceeds all possible payoffs from the deviation.

Front: weak dominance in a bayesian game
Back: [latex]
In a Bayesian game, an action $a_i^*$ weakly dominates $a_i$ if for any $\omega \in \Omega$, and any $\hat{a}_{-i}(\omega)$,
$$u_i [(a_i^* , (\hat{a}_{-i}(\omega)) , \omega] \geq u_i [(a_i , (\hat{a}_{-i}(\omega)) , \omega]$$
and for some $\omega \in \Omega$, and some $\hat{a}_{-i}(\omega)$,
$$u_i [(a_i^* , (\hat{a}_{-i}(\omega)) , \omega] > u_i [(a_i , (\hat{a}_{-i}(\omega)) , \omega]$$
[where $\hat{a}_{-i}(\omega)$ denotes the profile of actions taken by every player $(j,s_j(\omega)), j \neq i$ in state $\omega$. ]
Intuitive gloss: $a_i^*$ is optimal independently of what others know *and* do. The notion is stronger than weak dominance in a strategic game.[/latex]

Front: how to think of a strategy in a bayesian game
Back: [latex]
For player $i$: \\
a function from signals to actions: $f_i: T_i \rightarrow A_i$. \\
or\\
a function from the set of $i$-types to actions: $f_i : ((i,t_i)_{t_i \in T_i} \rightarrow A_i$. \\
or \\
a function from $\Omega$ to actions: $f_i: \Omega \rightarrow A_i$, such that if $s_i(\omega)=s_i(\omega')=t_i \in T_i$ then $f_i(\omega)=f_i(\omega')=a_i \in A_i$.
[/latex]

Front: summary of Enforceability and equilibrium

Front: perfect bayesian equilibrium
Back: where

Front: PBE existence

Front: technique for PBE
Back: go through all possible candidates for a PBE:
* pooling strategies: players do not condition on their signals from nature
* separating strategies: players do condition on their signals from nature
in typical beer-quiche game, 2 pooling strategies and 2 separating strategies. often one of the pooling strategies does not satisfy the intuitive criterion

Front: risk dominant equilibrium
Back: among pure-strategy equilibria, the risk dominant eqbm is the eqm with the highest deviation-payoff product, defined in two-strategy games as the product across the players of the difference between the eqm payoff and the payoff from deviating to the other strategy.

Front: experimental evidence about the distribution of Level-k types in the population
Back: eg Nagel (1995) finds that in a beauty contest game, most players are level 1 or 2

Front: style of proof for minmax payoffs